package Sort;

/**
 * @author shy_black
 * @date 2019/3/9 17:56
 * @Description:在插入排序中加入二分查找提高效率
 * 优化：寻找插入位置，从中间值开始比较（二分查找）
 * 二分：在一个有序数据集上，将带比较元素与中间位置元素比较，若小于中间位置元素
 * 则要插入的位置一定在中间位置前面，否则在中间位置的后边
 */
public class 插入排序_优化 {
    public static int[] binaryInsertSort(int arr[]) {
        int n = arr.length;
        if(n <= 1)
            return arr;
        for(int i = 1;i < n; i++) {
            //已排序空间的第一个元素
            int val = arr[i];
            int low = 0;
            int high = i-1;
            int j = i - 1;
            //寻找待插入位置
            while(low <= high) {
                //寻找中间位置
                int mid = (low + high ) / 2;
                if(arr[mid] < val) {
                    low = mid +1;
                }else {
                    high = mid -1;
                }
            }
            //已找到插入位置high+1
            for(;j>= high+1;j--) {
                arr[j+1] = arr[j];
            }
            arr[j+1] = val;
        }
        return arr;
    }
    public static void main(String[] args) {
        int[] arr = new int[]{5,4,3,2,6,5,5,1};
        arr = binaryInsertSort(arr);
        for(int i:arr) {
            System.out.print(i + "_");
        }
    }
}
